package com.antball.data.insert;

import sun.java2d.pipe.RegionIterator;

import java.util.Arrays;

/**
 * sort_by_half_insert   BinaryInsertSort  BinarySearch
 * @Auther: huangsj
 * @Date: 2019/9/17 16:22
 * @Description:
 */
public class BinaryInsertSort {

    public static void insertSort2(int[] a) {
        for (int i = 1; i < a.length; i++) {

            System.out.println("--------" + i + "---------");
            int left = 0;
            int right = i - 1;
            int curr = a[i];
            // 利用折半查找插入位置
            while (left <= right) {
                // 取中点
                int mid = (left + right) / 2;
                System.out.println("curr:" + curr + "  left:" + left + "   right:" + right + "   mid_index:" + mid + "-" + a[mid]);

                // 插入值小于中点值
                if (a[mid] > curr) {
                    // 向左缩小区间
                    right = mid - 1;
                } else {
                    // 向右缩小区间
                    left = mid + 1;
                }
            }
            System.out.println("curr:" + curr + "  left:" + left + "   right:" + right );

//            for(int j = i-1; j >= right+1; j--)
            // left即为找到的要插入的位置，所以下边的循环将left-(i-1)位置的元素依次向后移动
            for (int j = i - 1; j >= left; j--)
            {
                a[j + 1] = a[j];
            }

            // 将temp插入到left位置
            a[left] = curr;
            System.out.println(Arrays.toString(a));
        }
    }

    public static void main(String[] args) {
//        int[] a= new int[]{2,5,3,7};

//        int[] a = {7, 2, 5, 3, 1, 9, 4};
        int[] a = {1, 2, 9, 11, 31, 42, 47, 17, 3, 10, 15};
        System.out.println(a.length);
        System.out.println("--------0---------");
        System.out.println(Arrays.toString(a));
        insertSort2(a);
    }



//    public void insert(int[] arr){
//        for(int i = 1; i < arr.length; i++){
//            int key = arr[i];
//            int low = BinarySearch(arr,key,0,i-1);
//
//            for(int j = i-1; j >= low; j--)
//                arr[j+1] = arr[j];
//            arr[low] = key;
//        }
//    }
//
//    public int BinarySearch(int[] arr, int key, int low, int high){
//        while(low <= high){
//            int mid = ((high-low) >> 1) + low;
//            if(key < arr[mid])
//                high = mid - 1;
//            else
//                low = mid + 1;
//        }
//        return low;
//    }
}
